2016-06-17

The Full Counting Sort

完整的计数排序

In this challenge you need to print the data that accompanies each integer in a list. In addition, if two strings have the same integers, you need to print the strings in their original order. Hence, your sorting algorithm should be stable, i.e. the original order should be maintained for equal elements.

Insertion Sort and the simple version of Quicksort were stable, but the faster in-place version of Quicksort was not (since it scrambled around elements while sorting).

In cases where you care about the original order, it is important to use a stable sorting algorithm. In this challenge, you will use counting sort to sort a list while keeping the order of the strings (with the accompanying integer) preserved.
在本次任务中你将列表中与整数相关的数据。另外，如果两个字符串对应的整数相同，那么你需要按原来字符串出现的顺序打印它们。因此，你的排序算法必须是稳定的。意即，对于相同的元素必须维持其原来的先后顺序。

Challenge （任务）

In the previous challenge, you created a “helper array” that contains information about the starting position of each element in a sorted array. Can you use this array to help you create a sorted array of the original list?

Hint: You can go through the original array to access the strings. You can then use your helper array to help determine where to place those strings in the sorted array. Be careful about being one off.

Details and a Twist
You will be given a list that contains both integers and strings. Can you print the strings in order of their accompanying integers? If the integers for two strings are equal, ensure that they are print in the order they appeared in the original list.

The Twist - Your clients just called with an update. They don’t want you to print the first half of the original array. Instead, they want you to print a dash for any element from the first half.
在上一任务中，你创建了一个辅助数组，其中包含排序后数组中每个元素的起始位置信息。你能否利用此数组获得原列表的排序后的数组呢？

提示：你可以遍历原数组来访问获取字符串。你可以利用你的辅助数组来帮助你确定将字符串放到排序后的数组中的具体位置。注意记得减1.

细节和Twist：
给你一个包含整数和字符串的列表。你能按照整数的排序顺序打印出对应的字符串吗？如果两个整数一样，那么按照原来列表中出现的顺序打印。

Twist：你的客户刚刚电话要求更新要求。他们不希望你打印原列表的前半部分。相反的，他们希望你将前半部分的任何一个元素用破折号“-”替换。

Input Format （输入格式）

n, the size of the list ar.
n lines follow, each containing an integer x and a string s.
列表大小n
接下来n行，每行包含一个整数x和一个字符串s
Output Format （输出格式）
Print the strings in their correct order.
按正确的顺序打印字符串
Constraints （约束条件）
100<=n<=10^6
0<=x<100
n is even
1<=length(s) <=10
n是偶数

The characters in every string in lowercase.
字符串中所有字符为小写

Sample Input(输入样例)

20
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the

Sample Output（输出样例）

1	- - - - - to be or not to be - that is the question - - - -

Explanation （解释）

Below is the list in the correct order. The strings of each number were printed above for the second half of the array. Elements from the first half of the original array were replaced with dashes.
下面是正确的排序。
0 ab
0 ef
0 ab
0 ef
0 ij
0 to
1 be
1 or
2 not
2 to
3 be
4 ij
4 that
4 is
4 the
5 question
6 cd
6 gh
6 cd
6 gh

int c[100],a[1000001];
string s[1000001],r[1000001];
int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>s[i];
        if (i<n / 2){
            s[i]="-";
        }
        c[a[i]]++;
    }
    c[0]--;
    for(int i=1;i<100;i++){
        c[i]+=c[i-1];
    }
    for(int i=n-1;i>=0;i--){
        r[c[a[i]]]=s[i];
        c[a[i]]--;
    }
    for(int i=0;i<n;i++){
        cout<<r[i]<<" ";
    }
    return 0;
}

Challenge （任务）

Input Format （输入格式）

Output Format （输出格式）

Constraints （约束条件）

Sample Input(输入样例)

Sample Output（输出样例）

Explanation （解释）